package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/25 20:28
 * @description <p>链表中环的入口节点</p>
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：如果一个链表中包含环，那么应该如何找出环的入口节点？从
 * 链表的头节点开始顺着 next 指针方向进入环的第 1 个节点为环的入口节点。
 * 例如，在如图 4.3 所示的链表中，环的入口节点是节点 3。
 */
public class toOffer4_3_22 {
    public static void main(String[] args) {

        //初始化链表
        ListNode node0 = new ListNode(3);
        ListNode node1 = new ListNode(2);
        node0.next = node1;
        ListNode node2 = new ListNode(0);
        node1.next = node2;
        ListNode node3 = new ListNode(-4);
        node2.next = node3;
        node3.next = node1;

        System.out.println(detectCycle(node0).getVal());
    }

    /**
     * 方法二：快慢指针
     * <p>
     * 设：
     * 链表内非环的节点数 = x
     * 链表内环的总节点数 = y
     * 第一次相遇时候，慢指针走过的环里的节点数 = a
     * 第一次相遇时候，快指针走过的环里的节点数 = n*y+a （多走了n圈、n>=1）
     * <p>
     * 思路：
     * 快指针走2步、慢指针走一步。那么相遇的时候，S(快指针走过的路数) = 2 * (慢指针走过的节点数)
     * 所以 2*(x+a) = x+ny+a 即 x+a = ny
     * 那么证明：慢指针走过的节点数是链表内环的总节点数x的整数倍；快指针指针走过的节点数也是链表内环的总节点数x的整数倍
     * 可以让一个新的left指针指向头节点，另一个新的right指针指向前面快慢指针相遇的节点，它们同时都只走一个节点
     * 当新的left和right第一次相遇的时候，就是在环的入口相遇
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        //判空
        if (head == null){
            return null;
        }
        //初始化指针
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null){

            if (fast.next != null){
                fast = fast.next.next;
            }else {
                return null;
            }
            slow = slow.next;
            if (fast == slow){
                ListNode ptr = head;
                while (ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    /**
     * 方法一：垃圾方法，时间空间复杂度很高
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle1(ListNode head) {
        //初始化哨兵
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;

        Map<ListNode, Integer> map = new HashMap<>();
        while (node.next != null) {
            map.put(node, map.getOrDefault(node, 0) + 1);
            //只有map里面存在这对kv，并且v的值大于1，才能说有重复的值即存在环形链表
            if (map.containsKey(node) && map.get(node) > 1) {
                return node;
            }
            node = node.next;
        }

        return null;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public int getVal() {
            return this.val;
        }
    }
}
